#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>

#define SYMBOL       1
#define VECTOR       2
#define PAIR         16
#define COMMA        symbol("COMMA")
#define COMMA_AT     symbol("COMMA-AT")
#define BQ           symbol("BACKQUOTE")
#define BQ_LIST      symbol("BQ-LIST")
#define BQ_APPEND    symbol("BQ-APPEND")
#define BQ_QUOTE     symbol("BQ-QUOTE")

#define  EOS    0
//#define  SEXP   "( a ( b \"1 2 3\"@01) \"123\"@01 sdf334 )"
//#define  SEXP   "(BACKQUOTE 1)"
//#define  SEXP   "(BACKQUOTE (1 2 3))"
//#define  SEXP   "(BACKQUOTE (1 (COMMA X) 2))"
//#define  SEXP   "(BACKQUOTE (1 (COMMA-AT X) 2))"
//#define  SEXP   "(BACKQUOTE (1 (2 (COMMA X) 3) 4))"
#define  SEXP   "(BACKQUOTE (1 2 . 3))"

static char *source;
static char *pointer;
static struct sexp *nil;

struct pair {
    struct sexp *car;
    struct sexp *cdr;
};

struct sexp {
    int type;
    union {
        char* atom;
        struct pair *pr;
    };
};


void eat_comments() {
    while ((*pointer != EOS) && (*pointer != '\n')) {
        pointer++;
    }
}

void eat_whitespace() {
    while (*pointer != EOS) {
        if (isspace(*pointer)) {
            pointer++;
            continue;
        }
        if (*pointer == ';') { /* comments are whitespace also */
            eat_comments();
            continue;
        }
        else {
            break;
        }
    }
}

int is_delimiter(int c) {
    return isspace(c) || c == EOF ||
           c == '('   || c == ')' ||
           c == '"'   || c == ';';
}

int is_digit(int c) {
    return ((char)c) >= '0' && ((char)c) <= '9';
}

int digit_value(int c) {
    return c - ((int) '0');
}

int read_enum() {
    int r = 0;
    while(is_digit(*pointer)) {
        r = r << 4 + digit_value(*pointer);
        pointer++;
    }
    return r;
}

char* read_string() {
    int i = 0;
    char *buffer = (char *)malloc(1024 * sizeof(char));

    pointer++;
    while (*pointer != '"') {
        if (*pointer == '\\') {
            pointer++;
            if (*pointer == 'n') {
                *buffer++ = '\n'; // c=\t, c=\\, c=\" ...
            }
        }
        if (*pointer == EOS) {
            printf("Error while read atom!");
        }
        if (i < 1024 - 1) {
            buffer[i++] = *pointer;
        }
        else {
            printf("Error while read atom!");
        }
        pointer++;
    }
    pointer++;
    buffer[i] = '\0';
    return buffer;
}

char* read_operator() {
    int i = 0;
    char *buffer = (char *)malloc(1024 * sizeof(char));
    while (!is_delimiter(*pointer)) {
        if (*pointer == EOS) {
            printf("Error while read operator!");
        }
        if (i < 1024 - 1) {
            buffer[i++] = *pointer;
        }
        else {
            printf("Error while read operator!");
        }
        pointer++;
    }
    buffer[i] = '\0';
    return buffer;
}

char* read_literal() {
    char* lex_string = read_string();
    if (*pointer != '@') {
        printf("Error while read literal!");
    }
    pointer++;
    int type = read_enum();
    return lex_string;
    //return lex(type, lex_string);
}

void *token() {
    eat_whitespace();
    if (*pointer == EOS) {
        return 0;
    } else if (*pointer == '(') {
        pointer++;
        return "(";
    } else if (*pointer == ')') {
        pointer++;
        return ")";
    } else if (*pointer == '.') {
        pointer++;
        return ".";
    } else if (*pointer == '"') {
        return read_literal();
    } else {
        return read_operator();
    }
}

void *peek_token() {
    char *token_pointer = pointer;
    void* t = token();
    pointer = token_pointer;
    return t;
}

struct sexp *bq_completely_process(struct sexp *x);
void *list();
struct sexp *symbol(char* string);
int equals_atom(struct sexp *a, struct sexp *b);

void *datum() {
    eat_whitespace();
    if (*pointer == '(') {
        struct sexp *lst = list();
//        if (equals_atom(lst->pr->car, symbol("BACKQUOTE"))) {
//            lst = bq_completely_process(lst->pr->cdr);
//        }
        return lst;
    } else {
        struct sexp *t = (struct sexp *)malloc(sizeof(struct sexp));
        t->type = SYMBOL;
        t->atom = token();
        return t;
    }
}

void* single_list(void* d) {
    struct sexp *lst = (struct sexp *)malloc(sizeof(struct sexp));
    lst->type = PAIR;
    lst->pr = (struct pair *)malloc(sizeof(struct pair));
    lst->pr->car = d;
    lst->pr->cdr = nil;
    return lst;
}

void *list() {
    char *lparen = 0;
    char *rparen = 0;
    char *next = 0;
    struct sexp *node = 0;
    char c = 0;
    void *d = 0;
    void *e = 0;
    void *lst = 0;
    struct sexp *the_cdr = 0;

    eat_whitespace();
    lparen = token();
    if (lparen && *lparen != '(') {
        printf("error!");
    }
    next = peek_token();
    if (next && *next == ')') {
        token();
        return nil;
    }
    else {
        d = datum();

        int transform = 0;
        if (equals_atom(d, symbol("BACKQUOTE"))) {
            transform = 1;
        }

        lst = single_list(d);
        the_cdr = lst;
        while (1) {
            eat_whitespace();
            c = *pointer;
            if (c == ')' || c == '.') {
                break;
            }
            e = datum();
            the_cdr->pr->cdr = single_list(e);
            the_cdr = the_cdr->pr->cdr;
        }
        if (c == '.') {
            token(); //pointer++;
            the_cdr->pr->cdr = datum();
        }
        rparen = token();
        if (rparen && *rparen != ')') {
            printf("error!");
        }

        if (transform) {
            lst = bq_completely_process(((struct sexp *)lst)->pr->cdr->pr->car);
        }

        return lst;
    }
}

void print_sexp(struct sexp *exp) {
    struct sexp *t = exp;

    if (exp->type == 1) {
        printf("%s", exp->atom);
    } else if  (exp->type == 16) {
        printf("( ");
        while (1) {
            if (t->type != 16) break;
            if (t->pr->cdr->type == -1) break;
            if (t->type == 16) {
                print_sexp(t->pr->car);
            }
            else {
                print_sexp(t);
            }

            if (t->type == 16) {
                if (t->pr->cdr->type != 16) {
                    printf(" . ");
                } else {
                    printf(" ");
                }
            }
            t = t->pr->cdr;
        }
        if (t->type == 16) {
            print_sexp(t->pr->car);
        }
        else {
            print_sexp(t);
        }

//        print_sexp(exp->p->car);
//        printf(" . ");
//        print_sexp(exp->p->cdr);

        printf(" )");
    } else if  (exp->type == -1) {
        printf("()");
    } else {
        perror("error!");
    }
}


static struct sexp *nil;

struct sexp *bq_process(struct sexp *x);
struct sexp *bq_remove_tokens(struct sexp *x);
struct sexp *bracket(struct sexp *x);

int strcmp(const char *str1,const char *str2)
{
    while(*str1 == *str2)
    {
        if(*str1 == '\0')
            return 0;

        str1++;
        str2++;
    }
    return *str1 - *str2;
}


struct sexp *bq_completely_process(struct sexp *x) {
    struct sexp *raw_result = bq_process(x);
    return bq_remove_tokens(raw_result);
}

struct sexp *nreconc(struct sexp **lst, struct sexp *tail) {
    struct sexp *p = *lst;
    struct sexp *m = *lst;
    struct sexp *n = *lst;

    if (*lst == nil) {
        *lst = tail;
        return tail;
    }

    p = p->pr->cdr;
    while (p != nil) {
        m = p;
        p = p->pr->cdr;
        m->pr->cdr = n;
        n = m;
    }
    (*lst)->pr->cdr = tail;
    *lst = m;
    return m;
}

struct sexp *symbol(char* string) {
    struct sexp *s = (struct sexp *)malloc(sizeof(struct sexp));
    s->type = SYMBOL;
    s->atom = string;
}

struct sexp *vector_to_list(struct sexp *x) {
    return x; //todo
}

struct sexp *cons(struct sexp *a1, struct sexp *a2) {
    struct sexp *c = (struct sexp *)malloc(sizeof(struct sexp));
    c->type = PAIR;
    c->pr = (struct pair *)malloc(sizeof(struct pair));
    c->pr->car = a1;
    c->pr->cdr = a2;
    return c;
}

struct sexp *list_1(struct sexp *a1) {
    struct sexp *lst = (struct sexp *)malloc(sizeof(struct sexp));
    lst->type = PAIR;
    lst->pr = (struct pair *)malloc(sizeof(struct pair));
    lst->pr->car = a1;
    lst->pr->cdr = nil;
    return lst;
}

struct sexp *list_2(struct sexp *a1, struct sexp *a2) {
    struct sexp *lst = (struct sexp *)malloc(sizeof(struct sexp));
    lst->type = PAIR;
    lst->pr = (struct pair *)malloc(sizeof(struct pair));
    lst->pr->car = a1;
    lst->pr->cdr = (struct sexp *)malloc(sizeof(struct sexp));
    lst->pr->cdr->type = PAIR;
    lst->pr->cdr->pr = (struct pair *)malloc(sizeof(struct pair));
    lst->pr->cdr->pr->car = a2;
    lst->pr->cdr->pr->cdr = nil;
    return lst;
}

int equals_atom(struct sexp *a, struct sexp *b) {
    return (a->type != PAIR && b->type != PAIR && strcmp(a->atom, b->atom) == 0);
}

struct sexp *bq_process(struct sexp *x) {
    void *result;
    if (x->type != PAIR) {
        if (x->type == VECTOR) {
            result = list_2(symbol("list-to-vector"), bq_process(vector_to_list(x)));
        }
        else {
            result = list_2(BQ_QUOTE, x);
        }
        return result;
    }
    else if (equals_atom(x->pr->car, symbol("backquote"))) {
        return bq_process(bq_completely_process(x->pr->cdr->pr->car)); //car(cdr(x))
    }
    else if (equals_atom(x->pr->car, COMMA)) {
        return x->pr->cdr->pr->car;
    }
    else if (equals_atom(x->pr->car, COMMA_AT)) {
        //error(",@~S after `", x->pr->cdr->pr->car);
        perror("COMMA_AT after BQ_QUOTE");
        exit(0);
    }
    else {
        struct sexp *p = x;
        struct sexp *q = nil;

        while(1) {
            if (p->type != PAIR) {
                return cons(BQ_APPEND, nreconc(&q, list_1(list_2(BQ_QUOTE, p))));
            }
            if (equals_atom(p->pr->car, COMMA)) {
                if (p->pr->cdr->pr->cdr == nil) {
                    //error("Malformed ,~S", p);
                    perror("Malformed");
                    exit(0);
                }
                return cons(BQ_APPEND, nreconc(&q, list_1(p->pr->cdr->pr->car)));
            }
            if (equals_atom(p->pr->car, COMMA_AT)) {
                //error("Dotted ,@~S", p);
                perror("Dotted");
                exit(0);
            }

            q = cons(bracket(p->pr->car), q);
            p = p->pr->cdr;
        }
    }
}

int equals(struct sexp *a, struct sexp *b) {
    if (a == nil && b == nil) {
        return 1;
    }
    if (a == nil || b == nil) {
        return 0;
    }
    if (a->type != b->type) {
        return 0;
    }
    if (a->type != PAIR) {
        return strcmp(a->atom, b->atom) == 0;
    }
    else {
        return equals(a->pr->car, b->pr->car) && equals(a->pr->cdr, b->pr->cdr);
    }
}

// jalr $v0
struct sexp *maptree(struct sexp* (*fn)(struct sexp *x), struct sexp *x) {
    if (x->type != PAIR) {
        return fn(x);
    }
    else {
        struct sexp *a = fn(x->pr->car);
        struct sexp *d = maptree(fn, x->pr->cdr);

        if (equals(a, x->pr->car) && equals(d, x->pr->cdr)) {
            return x;
        }
        else {
            return cons(a, d);
        }
    }
}

struct sexp * bq_remove_tokens(struct sexp * x) {
    if (equals_atom(x, BQ_LIST)) {
        return symbol("list");
    }
    else if (equals_atom(x, BQ_APPEND)) {
        return symbol("append");
    }
    else if (equals_atom(x, BQ_QUOTE)) {
        return symbol("quote");
    }
    else if (x->type != PAIR) {
        return x;
    }
    else if (equals_atom(x->pr->car, BQ_LIST) && x->pr->cdr->pr->cdr->type == PAIR && x->pr->cdr->pr->cdr->pr->cdr == nil) {
        return cons(symbol("cons"), maptree(bq_remove_tokens, x->pr->cdr));
    }
    else {
        return maptree(bq_remove_tokens, x);
    }
}

struct sexp *bracket(struct sexp *x) {
    if (x->type != PAIR) {
        return list_2(BQ_LIST, bq_process(x));
    }
    else if (equals_atom(x->pr->car, COMMA)) {
        return list_2(BQ_LIST, x->pr->cdr->pr->car);
    }
    else if (equals_atom(x->pr->car, COMMA_AT)) {
        return x->pr->cdr->pr->car;
    }
    else {
        return list_2(BQ_LIST, bq_process(x));
    }
}

int main() {
    //$a0  contains file_name

    nil = (struct sexp *)malloc(sizeof(struct sexp));
    nil->type = -1;
    nil->atom = "";

    source = (char *)malloc(1024 * sizeof(char));
    strcpy(source, SEXP);
    pointer = source;

    void* result = list();
    print_sexp(result);
    return 0;
}
